1
等式约束的最优性条件
MATH008Lesson 10
00:00
想象一个物理系统,比如悬挂的链条,正试图达到最低能量状态。如果两端被固定,系统就无法自由移动。当内部力(势能梯度)与约束施加的张力力完全平衡时,即达到最优。在凸优化中,这种平衡由 KKT 条件 等式约束下的情况所捕捉。

可行性几何结构

对于具有等式约束 $Ax=b$ 的凸问题,向量 $v \in \mathbf{R}^n$ 是一个 可行方向 如果 $Av = 0$。这意味着沿方向 $v$ 移动不会破坏约束:若 $Ax = b$,则 $A(x+v) = b$。

为使 $x^*$ 最优,对所有属于零空间 $\mathcal{N}(A)$ 的可行方向 $v$,方向导数 $\nabla f(x^*)^T v$ 必须为零。这表明梯度 $\nabla f(x^*)$ 必须与 $\mathcal{N}(A)$ 正交,从而引出 拉格朗日乘子的存在。

最优性条件

当且仅当存在向量 $\nu^* \in \mathbb{R}^p$ 使得:

$\nabla f(x^*) + A^T \nu^* = 0$

该方程组刻画了目标函数下降趋势与约束流形之间的平衡状态。

投影梯度

欧几里得投影 负梯度 $-\nabla f(x)$ 在零空间 $\mathcal{N}(A)$ 上的投影定义为:

$\Delta x_{\text{pg}} = \text{argmin}_{Au=0} \| -\nabla f(x) - u \|_2$

该向量代表“最佳”的可行下降方向。关键在于,当且仅当 $\Delta x_{\text{pg}} = 0$ 时,点 $x$ 才是最优的。

KKT 系统与矩阵性质

我们可以通过分块系统同时求解牛顿步和对偶变量:

$$\begin{bmatrix} I & A^T \\ A & 0 \end{bmatrix} \begin{bmatrix} v \\ w \end{bmatrix} = \begin{bmatrix} -\nabla f(x) \\ 0 \end{bmatrix}$$

关于矩阵谱性质的说明: KKT 矩阵是对称的,但 不定的。若该矩阵非奇异,则它恰好有 $n$ 个正特征值和 $p$ 个负特征值。这意味着最优点 $(x^*, \nu^*)$ 是拉格朗日函数 $L(x, \nu) = f(x) + \nu^T(Ax-b)$ 的一个 鞍点 ,而非联合原-对偶空间中的简单局部极小值。

🎯 核心原理
等式约束问题中的最优性要求梯度与约束的零空间正交。这使我们可以将牛顿步解释为对 KKT 条件线性化近似问题的解。